package problem15_3SUM;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class MySolution {
	public static void main(String[] args){
		System.out.println(new MySolution().threeSum(new int[]{3,0,-2,-1,1,2}));
	}
	
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result=new LinkedList<>();
		if(nums.length<3) return result;
		Arrays.sort(nums);
		for(int i=0;i<nums.length-2;i++){
			int j=i+1,k=nums.length-1;
			while(j<k){
				int sum=nums[i]+nums[j]+nums[k];
				if(sum<0){
					j++;
				}else if(sum==0){
					result.add(Arrays.asList(nums[i],nums[j],nums[k]));
					while(j<k&&nums[j++]==nums[j]){}
					while(j<k&&nums[k--]==nums[k]){}
				}else{
					k--;
				}
			}
			while(i<nums.length-2&&nums[i++]==nums[i]){}
			i--;
		}
		return result;
	}
}
